package 二叉树;


//110 平衡二叉树
//记住此题需要自底向上，而不能常规思维自顶向下，否则会有大量的求深度的冗余。
//时间复杂的O（n）
public class Solution6 {

    /**
     * 主函数，作为递归的入口。
     * @param root 树的根节点
     * @return 如果树是平衡的，返回 true；否则返回 false。
     */
    public boolean isBalanced(TreeNode root) {
        // 调用辅助递归函数。
        // 如果返回的高度不是-1，说明整棵树都是平衡的。
        // 如果是-1，说明在某个子树上已经发现了不平衡。
        return getHeight(root) != -1;
    }

    /**
     * 辅助递归函数 (后序遍历)。
     * 它的职责是：
     * 1. 如果以 node 为根的子树是平衡的，则返回它的实际高度。
     * 2. 如果以 node 为根的子树是不平衡的，则返回 -1 作为“不平衡”的信号。
     *
     * @param node 当前节点
     * @return 子树的高度 或 -1 (如果不平衡)
     */
    private int getHeight(TreeNode node) {
        // Base Case: 空树是平衡的，其高度为 0。
        if (node == null) {
            return 0;
        }

        // 1. 递归计算左子树的高度 (后序遍历)
        int leftHeight = getHeight(node.left);
        // 【剪枝】如果左子树已经报告了不平衡，我们无需再检查右子树。
        // 立刻将“-1”这个“坏消息”向上传递，终止后续不必要的计算。
        if (leftHeight == -1) {
            return -1;
        }

        // 2. 递归计算右子树的高度 (后序遍历)
        int rightHeight = getHeight(node.right);
        // 【剪枝】如果右子树报告了不平衡，同样立刻传递“坏消息”。
        if (rightHeight == -1) {
            return -1;
        }

        // 3. 处理当前节点 (在左右子树都处理完之后)
        // 检查当前节点是否平衡
        if (Math.abs(leftHeight - rightHeight) > 1) {
            // 如果当前节点不平衡，发出“-1”信号
            return -1;
        }

        // 如果当前节点是平衡的，则返回它的真实高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
}
